package _interview100;

import java.util.Arrays;

/**
 * 198. 打家劫舍
 */
public class No198 {
    private int[] nums;
    private int[] cache;

    public int rob(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        cache = new int[n];
        Arrays.fill(cache, -1);
        return dfs(n - 1);
    }

    private int dfs(int i) {
        if (i < 0) return 0;
        else if (cache[i] != -1) return cache[i];
        else return cache[i] = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);
    }
}
